/**
 * leetcode #2610
 *
 * 贪心原则的核心思想:
 *  在每一步选择中都采娶当前状态下最优的选择，希望通过一系列局部最优解的组合，达到全局最优解 
 * 
 *  std::map 和 std::unordered_map的区别：
 *                  std::map        std::unordered_map
 *  底层实现:           红黑树            哈希表
 *  排序特性            按键排序          无序
 *  增删找时间复杂度    O(log n)        平均O(1)
 *  
 */

#include <vector>
#include <algorithm>
#include <iostream>
#include <unordered_map>

using namespace std;

// 暴力解法
namespace S1 {
    class Solution {
    public:
        vector<vector<int>> findMatrix(vector<int>& nums) {
            vector<vector<int>> res;
            for (auto& num : nums) {
                for (int i = 0; i < nums.size(); i ++) {
                    if (i >= res.size()) {
                        res.emplace_back(vector<int>());
                    }
                    if (res[i].empty()) {
                        res[i].emplace_back(num);
                        break;
                    } else {
                        auto b = std::find(res[i].begin(), res[i].end(), num);
                        if (b == res[i].end()) {
                            res[i].emplace_back(num);
                            break;
                        }
                    }
                }
            }
            return res;
        }
    };
 }

 // 哈希表
 namespace S2 {
    class Solution {
        public:
        vector<vector<int>> findMatrix(vector<int>& nums) {
            // 1.用哈希表保存每个出现的次数
            unordered_map<int, int> cnt;
            for (int x : nums) {
                cnt[x]++;
            }
            // ?? 贪心原则
            vector<vector<int>> res;
            while (!cnt.empty()) {
                vector<int> arr;
                for(auto it = cnt.begin(); it != cnt.end(); ) {
                    it->second -= 1;
                    arr.emplace_back(it->first);
                    if (it->second == 0) {
                        it = cnt.erase(it);
                    } else {
                        it++;
                    }
                }
                res.emplace_back(arr);
            }
            return res;
        }
    };
}

namespace S3 {
    class Solution {
    public:
        vector<vector<int>> findMatrix(vector<int>& nums) {
            // 1.用哈希表保存每个出现的次数
            int n = 0;
            unordered_map<int, int> cnt;
            for (int x : nums) {
                cnt[x]++;
                n = max(n, cnt[x]);
            }

            //
            vector<vector<int>> res(n);

            for (int i = 0; i < n; i++) { // 相比S2 减少的外循环的次数
                for(auto&[k, v]: cnt) {
                    if (v > 0) {
                        res[i].push_back(k);     // 相比S2少了删除哈希表中的值，可能会引起哈希表的重新哈希增加一些开销
                        cnt[k]--;
                    }
                }
            }
            return res;
        }
    };
}

namespace S4 {
    class Solution {
    public:
        vector<vector<int>> findMatrix(vector<int>& nums) {
            // 1.用哈希表保存每个出现的次数
            int n = 0;
            unordered_map<int, int> cnt;
            for (int x : nums) {
                cnt[x]++;
                n = max(n, cnt[x]);
            }

            //
            vector<vector<int>> res(n);
            for(auto&[k, v]: cnt) {  // 相比S3 减少了内循环的次数
                for (int i = 0; i < v; i ++) {
                    res[i].push_back(k); 
                }
            }
            return res;
        }
    };
}

 int main() {
    S2::Solution s;
    vector<int> nums = {1,3,4,1,2,3,1};
    auto res = s.findMatrix(nums);

    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            std::cout << res[i][j] << ",";
        }
        std::cout << std::endl;
    }
 }